\chapter{Abstract syntax tree}
\label{chap-abstract-syntax-tree}

\section{Purpose}

The abstract syntax tree%
\footnote{An abstract syntax tree is not a tree, and not even an
  acyclic graph, but it is traditionally called an abstract syntax
  tree anyway, so we keep this terminology.}  (AST for short) is a
structured version of the source code in which the use for an
environment has been eliminated.%
\footnote{More traditional languages use the term \emph{abstract
    syntax tree} for a notation that is much closer to the source code
  than the notation we use here.}
An abstract syntax tree consists of a graph of standard objects.  Each
object class corresponds to some intrinsic category of source code
elements.

A lexical variable in the source code is represented in the AST by a
standard object that contains its name, but different variables with
the same name in the source code are represented by different object
instances.  Global functions and special variables are similarly
represented by standard objects that contain the name of the function
or variable.  Since different lexical variables with different names
are represented by different object instances, there is no need for
scoping operators such as \texttt{let} or \texttt{let*}, which is why
there are no classes that correspond to these source constructs.

Macros and symbol macros have been expanded, leaving a small set of
operators for constructing and calling functions, for binding special
variables, for assigning values to variables, etc.

There are no AST classes that correspond to declarations.
Implementations should replace type declarations by the use of
instances of the \texttt{the-ast} class or the \texttt{typeq-ast}
class as indicated by the \hs{}.

Functions that can not be expressed as simpler functions, and that are
performance critical, have been given their own abstract syntax trees.
For instance the function that given a \texttt{cons} cell returns the
\texttt{car} of that \texttt{cons} cell (this is only part of what the
\commonlisp{} function \texttt{car} does) has been given its own abstract
syntax tree class.  Implementations are under no obligation to use
these classes.  It is perfectly possible for an implementation to
represent every function call to a standard \commonlisp{} function by a
\texttt{call-ast}.  However, \sysname{} contains features that make it
easier to optimize the resulting code if these classes are used.

Implementations are free to create subclasses of the AST classes
listed here, for instance in order to add additional information to
AST nodes.  In that case, it might be necessary to provide overriding
or extending methods on the generic functions that handle the abstract
syntax tree, in particular when it is translated into HIR.

Implementations are also free to create entirely new AST classes.
Then it might be necessary to provide primary methods on some generic
functions that manipulate the abstract syntax tree.%
\fixme{At some point, provide a list of generic functions that would
  require overriding, extending, or primary methods.}

\section{Compilation policy}

All AST objects include a compilation policy \seechap{chap-policy},
specified by the initarg \texttt{:policy} and with accessor
\texttt{policy}. If many ASTs are being created at once, the
special variable \texttt{*policy*} can be bound, and will be used
as an initform.

\section{Classes of abstract syntax trees}

\subsection{General types of abstract syntax trees}

There is no abstract syntax tree class corresponding to the special
operator \texttt{eval-when}.  The compiler takes action based on the
context of the compilation and either evaluates or generates an
abstract syntax tree.

\subsubsection{\texttt{literal-ast}}
\label{literal-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:value} & \texttt{value} & The corresponding constant.\\
\hline
\end{tabular}

A \texttt{literal-ast} is typically used by an implementation to
represent constants in the source code.

This constant can either be in the form of a self-evaluating object,
the value of a constant variable, or a quoted object.

At this point, there is no discrimination between the different types
of constant, nor between integers of different magnitude.  Later on
in the compilation process, some backend may replace small integer
constants by immediate values.

\subsubsection{\texttt{fdefinition-ast}}
\label{fdefinition-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:name-ast} & \texttt{name-ast} & The name of the function.\\
\hline
\end{tabular}

The \texttt{fdefinition-ast} is produced whenever the compiler sees a
reference to a \emph{global function}, i.e., a name in a functional
position that is not defined as a local function, as a special
operator, nor as a macro.  It can also be produced as an inline
version of the function \texttt{fdefinition}.

The \texttt{name-ast} is an AST that produces the name of function.
It can be either a \texttt{literal-ast}, in which case the constant
is a function name, or it can be some other AST that evaluates to the
name of a function.  When the \texttt{fdefinition-ast} is produced as
a result of a name in the functional position of a form, then the
\texttt{name-ast} is always a \texttt{literal-ast}.

\subsubsection{\texttt{symbol-value-ast}}
\label{symbol-value-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:name-ast} & \texttt{name-ast} & The name of the variable.\\
\hline
\end{tabular}

A \texttt{symbol-value-ast} is produced whenever the compiler sees a
reference to a \emph{special variable}, i.e. a name in a variable
position that is not defined as a lexical variable, a constant
variable, nor as a symbol macro.  It can also be produced as an inline
version of the function \texttt{symbol-value}.

The \texttt{name-ast} is an AST that produces the name of the
variable.  It can be either a \texttt{literal-ast}, in which case the
constant is a symbol, or it can be some other AST that evaluates to a
symbol.  When the \texttt{symbol-value-ast} is produced as a result of
a reference to a special variable, then the \texttt{name-ast} is
always a \texttt{literal-ast}.

\subsubsection{\texttt{set-symbol-value-ast}}
\label{set-symbol-value-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:name-ast} & \texttt{name-ast} & The name of the variable.\\
\hline
\texttt{:value-ast} & \texttt{value-ast} & The value to be assigned.\\
\hline
\end{tabular}

A \texttt{set-symbol-value-ast} is produced whenever the compiler sees
an assignment to a \emph{special variable}.  It can also be produced
as an inline version of the function \texttt{(setf symbol-value)}.

The \texttt{name-ast} is an AST that produces the name of the
variable.  It can be either a \texttt{literal-ast}, in which case the
constant is a symbol, or it can be some other AST that evaluates to a
symbol.  When the \texttt{symbol-value-ast} is produced as a result of
an assignment to a special variable, then the \texttt{name-ast} is
always a \texttt{literal-ast}.

The \texttt{value-ast} is an AST that evaluates to the value to be
assigned to the variable.

This AST does not produce any value.  It must appear in a context
where no value is required, such as one of the forms preceding the
last form of a \texttt{progn-ast} \seesec{progn-ast}.

\subsubsection{\texttt{lexical-ast}}
\label{lexical-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:name} & \texttt{name} & The name of the variable.\\
\hline
\end{tabular}

A \texttt{lexical-ast} is produced whenever the compiler sees a
reference to a \emph{lexical variable}.

\subsubsection{\texttt{call-ast}}
\label{call-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:callee-ast} & \texttt{callee-ast} & The AST of the function
to be called\\
\hline
\texttt{:argument-asts} & \texttt{argument-asts} & A list of ASTs, one
for each argument\\
& & to the function.\\
\hline
\end{tabular}

A \texttt{call-ast} is produced whenever the compiler sees a function
call.  It contains ASTs for the function to be called and for the
arguments to that function.  The AST representing the function can be
any AST that produces a function as a value.

\subsubsection{\texttt{block-ast}}
\label{block-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:body-ast} & \texttt{body-ast} & The AST of the body.\\
\hline
\end{tabular}

The \texttt{block-ast} is used to represent the \commonlisp{} special operator
\texttt{block}.  The \texttt{block-ast} does not contain the name of
the block because the \texttt{return-from-ast} contains a reference to
the corresponding \texttt{block-ast}.

\subsubsection{\texttt{function-ast}}
\label{function-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:body-ast} & \texttt{body-ast} & The AST for the body of the function.\\
\hline
\texttt{:lambda-list} & \texttt{lambda list} & The lambda list of the function.\\
\hline
\end{tabular}

The \texttt{function-ast} is one of the more complicated ones, because
it hides all the implementation details of how arguments are parsed.

\subsubsection{\texttt{tagbody-ast}}
\label{tagbody-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:item-asts} & \texttt{item-asts} & A list of ASTs corresponding to\\
& & the items of the \texttt{tagbody} form. \\
\hline
\end{tabular}

An item can either be a \texttt{tag-ast} or an AST corresponding to
some \texttt{statement}.

\subsubsection{\texttt{tag-ast}}
\label{tag-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:name} & \texttt{name} & The name of the tag.\\
\hline
\end{tabular}

\subsubsection{\texttt{go-ast}}
\label{go-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:tag-ast} & \texttt{body-ast} & The AST for the tag.\\
\hline
\end{tabular}

The \texttt{go-ast} contains a reference to the corresponding
\texttt{tag-ast} in the \texttt{tagbody-ast} that the \texttt{go} form
in the source code refers to.

\subsubsection{\texttt{if-ast}}
\label{if-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:test-ast} & \texttt{body-ast} & The AST for the test.\\
\hline
\texttt{:then-ast} & \texttt{then-ast} & The AST for the \emph{then} branch.\\
\hline
\texttt{:else-ast} & \texttt{else-ast} & The AST for the \emph{else} branch.\\
\hline
\end{tabular}

The \texttt{if-ast} corresponds directly to the \commonlisp{} special operator
\texttt{if}.

\subsubsection{\texttt{load-time-value-ast}}
\label{load-time-value-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:form-ast} & \texttt{form-ast} & The AST of the form.\\
\texttt{:read-only-p} & \texttt{read-only-p} & The read-only-p argument.\\
\hline
\end{tabular}

A \texttt{load-time-value-ast} is produced whenever the compiler sees
a \texttt{load-time-value} special form.

This AST always contains a \emph{form-ast}, which is the result of the
translation of the \texttt{form} argument to the
\texttt{load-time-value} special operator.

\subsubsection{\texttt{progn-ast}}
\label{progn-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:form-asts} & \texttt{form-asts} & A list of ASTs of the body.\\
\hline
\end{tabular}

The \texttt{progn-ast} corresponds directly to the \commonlisp{} special
operator \texttt{progn}.  It returns the values that are return by the
last AST in the child forms.

\subsubsection{\texttt{return-from-ast}}
\label{return-from-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:block-ast} & \texttt{block-ast} & The AST of the
corresponding block.\\
\hline
\texttt{:form-ast} & \texttt{form-ast} & The AST of the value form.\\
\hline
\end{tabular}

\subsubsection{\texttt{setq-ast}}
\label{setq-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:lhs-ast} & \texttt{lhs-ast} & The AST of the left-hand side.\\
\hline
\texttt{:value-ast} & \texttt{value-ast} & The AST of the value form.\\
\hline
\end{tabular}

This AST does not produce any value.  It must appear in a context
where no value is required, such as one of the forms preceding the
last form of a \texttt{progn-ast} \seesec{progn-ast}.

\subsubsection{\texttt{the-ast}}
\label{the-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:form-ast} & \texttt{form-ast} & The first argument.\\
\hline
\texttt{:required} & \texttt{required-types} & Required types of the declaration.\\
\hline
\texttt{:optional} & \texttt{optional-types} & \optional types of the declaration.\\
\hline
\texttt{:rest} & \texttt{rest-type} & \rest type of the declaration.\\
\hline
\end{tabular}

This AST informs the compiler of a type declaration, for example
from \texttt{cl:the} or \texttt{cl:declare}. Its semantics are identical
to those of \texttt{cl:the}, with the exception that the values
type is completely explicit (no implicit \rest \texttt{t}).

This AST has no operational effect. Later stages of compilation may
insert an explicit type check, but this is not required by the AST.

Currently, \key types are not usable. This is a limitation.

\subsubsection{\texttt{typeq-ast}}
\label{typeq-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:type-specifier} & \texttt{type-specifier} & The type specifier.\\
\hline
\texttt{:type-specifier-ast} & \texttt{type-specifier-ast} & An AST for the type specifier (see below).\\
\hline
\texttt{:form-ast} & \texttt{form-ast} & The form with type checked.\\
\hline
\end{tabular}

This AST represents a branch based on the type of the primary value
returned by a form. It can only appear as the first child (the test)
of an \texttt{if-ast} \seesec{if-ast}.

The \texttt{type-specifier-ast} slot holds a \texttt{load-time-value-ast}\seesec{load-time-value-ast}
with the constant type specifier. This is used later in compilation in the case that the \texttt{typeq} must be implemented as a call to
\texttt{cl:typep}, and is computed from the type specifier automatically
if not provided.

\subsection{Abstract syntax trees for fixnum arithmetic}

\subsubsection{\texttt{fixnum-add-ast}}
\label{fixnum-add-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:arg1-ast} & \texttt{arg1-ast} & The first argument.\\
\hline
\texttt{:arg2-ast} & \texttt{arg2-ast} & The second argument.\\
\hline
\texttt{:variable-ast} & \texttt{variable-ast} & The variable in which to store the result.\\
\hline
\end{tabular}

This AST can be used by implementations that represent fixnums in a
way that allows them to be added directly without first unboxing
them.

This AST can only occur as the first child of an \texttt{if-ast}
\seesec{if-ast}.  It has three children.

The first and the second child are ASTs that represent the arguments
to the fixnum operation.  The third child is a
\texttt{lexical-ast} that will hold the result of the operation.

The semantics of this AST are that the operands are added and if the
outcome is \emph{normal}, i.e., there is no overflow, then the lexical
variable is assigned the result of the operation, i.e., the sum of the
two operands.  If the operation results in an \emph{overflow}, then
the lexical variable is still a fixnum representing the result of the
operation as follows:  If the result is \emph{negative}, then the
sum of the two operands is $2^n + r$ where $n$ is the number of bits
used to represent a fixnum, and $r$ is the value of the lexical
variable.  If the result is \emph{positive}, then the sum of the two
operands is $r - 2^n$.

\subsubsection{\texttt{fixnum-sub-ast}}
\label{fixnum-sub-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:arg1-ast} & \texttt{arg1-ast} & The first argument.\\
\hline
\texttt{:arg2-ast} & \texttt{arg2-ast} & The second argument.\\
\hline
\texttt{:variable-ast} & \texttt{variable-ast} & The variable in which to store the result.\\
\hline
\end{tabular}

This AST can be used by implementations that represent fixnums in a
way that allows them to be subtracted directly without first unboxing
them.

This AST can only occur as the first child of an \texttt{if-ast}
\seesec{if-ast}.  It has three children.

The first and the second child are ASTs that represent the arguments
to the fixnum operation.  The third child is a
\texttt{lexical-ast} that will hold the result of the operation.

The semantics of this AST are that the operands are subtracted and if
the outcome is \emph{normal}, i.e., there is no overflow, then the
lexical variable is assigned the result of the operation, i.e., the
difference between the two operands.  If the operation results in an
\emph{overflow}, then the lexical variable is still a fixnum
representing the result of the operation as follows: If the result is
\emph{negative}, then the difference between the two operands is $2^n
+ r$ where $n$ is the number of bits used to represent a fixnum, and
$r$ is the value of the lexical variable.  If the result is
\emph{positive}, then the difference between the two operands is $r -
2^n$.

\subsubsection{\texttt{fixnum-less-ast}}
\label{fixnum-less-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:arg1-ast} & \texttt{arg1-ast} & The first argument.\\
\hline
\texttt{:arg2-ast} & \texttt{arg2-ast} & The second argument.\\
\hline
\end{tabular}

This AST can be used by implementations that represent fixnums in a
way that allows them to be compared directly without first unboxing
them.

This AST can only occur as the first child (i.e., the \emph{test}) of
an \texttt{if-ast} \seesec{if-ast}.  It has two children that
represent the arguments to the comparison.

Semantically, this AST returns \emph{true} if an only if the first
argument is strictly less than the second (and \emph{false}
otherwise), except that since this AST can only occur in the test
position of an \texttt{if-ast}, no value will ever be returned.
Instead this AST translates to a test and a branch.

\subsubsection{\texttt{fixnum-not-less-ast}}
\label{fixnum-not-less-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:arg1-ast} & \texttt{arg1-ast} & The first argument.\\
\hline
\texttt{:arg2-ast} & \texttt{arg2-ast} & The second argument.\\
\hline
\end{tabular}

This AST can be used by implementations that represent fixnums in a
way that allows them to be compared directly without first unboxing
them.

This AST can only occur as the first child (i.e., the \emph{test}) of
an \texttt{if-ast} \seesec{if-ast}.  It has two children that
represent the arguments to the comparison.

Semantically, this AST returns \emph{true} if an only if the first
argument is not strictly less than the second (and \emph{false}
otherwise), except that since this AST can only occur in the test
position of an \texttt{if-ast}, no value will ever be returned.
Instead this AST translates to a test and a branch.

\subsubsection{\texttt{fixnum-greater-ast}}
\label{fixnum-greater-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:arg1-ast} & \texttt{arg1-ast} & The first argument.\\
\hline
\texttt{:arg2-ast} & \texttt{arg2-ast} & The second argument.\\
\hline
\end{tabular}

This AST can be used by implementations that represent fixnums in a
way that allows them to be compared directly without first unboxing
them.

This AST can only occur as the first child (i.e., the \emph{test}) of
an \texttt{if-ast} \seesec{if-ast}.  It has two children that
represent the arguments to the comparison.

Semantically, this AST returns \emph{true} if an only if the first
argument is strictly greater than the second (and \emph{false}
otherwise), except that since this AST can only occur in the test
position of an \texttt{if-ast}, no value will ever be returned.
Instead this AST translates to a test and a branch.

\subsubsection{\texttt{fixnum-not-greater-ast}}
\label{fixnum-not-greater-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:arg1-ast} & \texttt{arg1-ast} & The first argument.\\
\hline
\texttt{:arg2-ast} & \texttt{arg2-ast} & The second argument.\\
\hline
\end{tabular}

This AST can be used by implementations that represent fixnums in a
way that allows them to be compared directly without first unboxing
them.

This AST can only occur as the first child (i.e., the \emph{test}) of
an \texttt{if-ast} \seesec{if-ast}.  It has two children that
represent the arguments to the comparison.

Semantically, this AST returns \emph{true} if an only if the first
argument is not strictly greater than the second (and \emph{false}
otherwise), except that since this AST can only occur in the test
position of an \texttt{if-ast}, no value will ever be returned.
Instead this AST translates to a test and a branch.

\subsubsection{\texttt{fixnum-equal-ast}}
\label{fixnum-equal-ast}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:arg1-ast} & \texttt{arg1-ast} & The first argument.\\
\hline
\texttt{:arg2-ast} & \texttt{arg2-ast} & The second argument.\\
\hline
\end{tabular}

This AST can be used by implementations that represent fixnums in a
way that allows them to be compared directly without first unboxing
them.

This AST can only occur as the first child (i.e., the \emph{test}) of
an \texttt{if-ast} \seesec{if-ast}.  It has two children that
represent the arguments to the comparison.

Semantically, this AST returns \emph{true} if an only if the first
argument is equal to the second (and \emph{false} otherwise), except
that since this AST can only occur in the test position of an
\texttt{if-ast}, no value will ever be returned.  Instead this AST
translates to a test and a branch.

\subsection{Abstract syntax trees for floating-point arithmetic}
\label{sec-ast-floating-point-arithmetic}

The ASTs in this section can be used by implementation that want to
inline floating-point arithmetic.  Each AST requires arguments and
produces results of one and the same floating-point type.  The exact
type is indicated in a slot of the AST.

\subsubsection{\texttt{float-add-ast}}
\label{sec-ast-float-add}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.  The value of this AST is
the floating-point value of the type indicated by \texttt{subtype}
representing the sum of the two arguments.

\subsubsection{\texttt{float-sub-ast}}
\label{sec-ast-float-sub}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.  The value of this AST is
the floating-point value of the type indicated by \texttt{subtype}
representing the difference between the two arguments.

\subsubsection{\texttt{float-mul-ast}}
\label{sec-ast-float-mul}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.  The value of this AST is
the floating-point value of the type indicated by \texttt{subtype}
representing the product of the two arguments.

\subsubsection{\texttt{float-div-ast}}
\label{sec-ast-float-div}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.  The value of this AST is
the floating-point value of the type indicated by \texttt{subtype}
representing the quotient of the two arguments.

\subsubsection{\texttt{float-less-ast}}
\label{sec-ast-float-less}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.

An AST of this type can only occur as the \texttt{test-ast} of an
\texttt{if-ast}.  The \texttt{then-ast} of the \texttt{if-ast} is
evaluated if the first argument is strictly less than the second
argument.  Otherwise, the \texttt{else-ast} of the \texttt{if-ast} is
evaluated.

\subsubsection{\texttt{float-not-greater-ast}}
\label{sec-ast-float-not-greater}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.

An AST of this type can only occur as the \texttt{test-ast} of an
\texttt{if-ast}.  The \texttt{then-ast} of the \texttt{if-ast} is
evaluated if the first argument is less than or equal to the second
argument.  Otherwise, the \texttt{else-ast} of the \texttt{if-ast} is
evaluated.

\subsubsection{\texttt{float-greater-ast}}
\label{sec-ast-float-greater}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.

An AST of this type can only occur as the \texttt{test-ast} of an
\texttt{if-ast}.  The \texttt{then-ast} of the \texttt{if-ast} is
evaluated if the first argument is strictly greater than the second
argument.  Otherwise, the \texttt{else-ast} of the \texttt{if-ast} is
evaluated.

\subsubsection{\texttt{float-not-less-ast}}
\label{sec-ast-float-not-less}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.

An AST of this type can only occur as the \texttt{test-ast} of an
\texttt{if-ast}.  The \texttt{then-ast} of the \texttt{if-ast} is
evaluated if the first argument is greater than or equal to the second
argument.  Otherwise, the \texttt{else-ast} of the \texttt{if-ast} is
evaluated.

\subsubsection{\texttt{float-equal-ast}}
\label{sec-ast-float-equal}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument1-ast} & \texttt{argument1-ast} & The first argument.\\
\hline
\texttt{:argument2-ast} & \texttt{argument2-ast} & The second argument.\\
\hline
\end{tabular}

The arguments of this AST must evaluate to floating-point values of
the type indicated by the \texttt{subtype}.

An AST of this type can only occur as the \texttt{test-ast} of an
\texttt{if-ast}.  The \texttt{then-ast} of the \texttt{if-ast} is
evaluated if the first argument is equal to the second argument.
Otherwise, the \texttt{else-ast} of the \texttt{if-ast} is evaluated.

\subsubsection{\texttt{float-sin-ast}}
\label{sec-ast-float-sin}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument-ast} & \texttt{argument-ast} & The argument.\\
\hline
\end{tabular}

The argument of this AST must evaluate to a floating-point value of
the type indicated by the \texttt{subtype}.  The value of this AST is
the floating-point value of the type indicated by \texttt{subtype}
representing the \emph{sine} of the argument.

\subsubsection{\texttt{float-cos-ast}}
\label{sec-ast-float-cos}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument-ast} & \texttt{argument-ast} & The argument.\\
\hline
\end{tabular}

The argument of this AST must evaluate to a floating-point value of
the type indicated by the \texttt{subtype}.  The value of this AST is
the floating-point value of the type indicated by \texttt{subtype}
representing the \emph{cosine} of the argument.

\subsubsection{\texttt{float-sqrt-ast}}
\label{sec-ast-float-sqrt}

\begin{tabular}{|l|l|l|}
\hline
Initarg & Reader & Description\\
\hline\hline
\texttt{:subtype} & \texttt{subtype} & The exact floating-point type.\\
\hline
\texttt{:argument-ast} & \texttt{argument-ast} & The argument.\\
\hline
\end{tabular}

The argument of this AST must evaluate to a floating-point value of
the type indicated by the \texttt{subtype}.  The value of this AST is
the floating-point value of the type indicated by \texttt{subtype}
representing the \emph{square root} of the argument.

\subsection{Abstract syntax trees for operations on conses}

\subsubsection{\texttt{car-ast}}
\label{sec-ast-car}

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:cons-ast} & \texttt{cons-ast} & The cons.\\
  \hline
\end{tabular}

This AST can be used to implement the function \texttt{cl:car}. However,
it does not correspond exactly to the function \texttt{car}, because
the value of the single child must be a cons cell. The consequences
are undefined if this condition is not met.

\subsubsection{\texttt{cdr-ast}}
\label{sec-ast-cdr}

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:cons-ast} & \texttt{cons-ast} & The cons.\\
  \hline
\end{tabular}

This AST can be used to implement the function \texttt{cl:cdr}. However,
it does not correspond exactly to the function \texttt{cdr}, because
the value of the single child must be a cons cell. The consequences
are undefined if this condition is not met.

\subsubsection{\texttt{rplaca-ast}}
\label{sec-ast-rplaca}

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:cons-ast} & \texttt{cons-ast} & The cons.\\
  \hline
  \texttt{:object-ast} & \texttt{object-ast} & The object to be put in the \texttt{car}.\\
  \hline
\end{tabular}

This AST can be used to implement the function \texttt{cl:rplaca}.
This AST differs from the function \texttt{rplaca} in that it does
not generate any value. An attempt to compile this AST in a context
where a value is needed will result in an error being signaled.

\subsubsection{\texttt{rplacd-ast}}
\label{sec-ast-rplacd}

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:cons-ast} & \texttt{cons-ast} & The cons.\\
  \hline
  \texttt{:object-ast} & \texttt{object-ast} & The object to be put in the \texttt{cdr}.\\
  \hline
\end{tabular}

This AST can be used to implement the function \texttt{cl:rplacd}.
This AST differs from the function \texttt{rplacd} in that it does
not generate any value. An attempt to compile this AST in a context
where a value is needed will result in an error being signaled.

\subsubsection{\texttt{nook-read-ast}}
\label{sec-ast-nook-read}

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:object-ast} & \texttt{object-ast} & The AST for the object.\\
  \texttt{:nook-number-ast} & \texttt{nook-number-ast} & The AST for
  the nook number.\\
  \hline
\end{tabular}

This AST can be used to read a nook of a standard object.

\subsubsection{\texttt{nook-write-ast}}
\label{sec-ast-nook-write}

\begin{tabular}{|l|l|l|}
  \hline
  Initarg & Reader & Description\\
  \hline\hline
  \texttt{:object-ast} & \texttt{object-ast} & The AST for the object.\\
  \texttt{:nook-number-ast} & \texttt{nook-number-ast} & The AST for
  the nook number.\\
  \texttt{:value-ast} & \texttt{value-ast} & The AST for\\
  the value to be written.\\
  \hline
\end{tabular}

This AST can be used to write a nook of a standard object.

\section{A CLIM-based AST visualizer}

\subsection{Profiles and how to combine them}

\subsubsection{Concept and representation}

In order to compute a good layout of AST nodes so as to avoid wasting
too much whitespace, we need to pack these nodes.  For this purpose,
we use the concept of a \emph{profile} indicated in
\refFig{fig-profile}.

\begin{figure}
\begin{center}
\inputfig{fig-profile.pdf_t}
\end{center}
\caption{\label{fig-profile}
A profile.}
\end{figure}

As \refFig{fig-profile} suggests, the upper-left cordner of a profile
is always at coordinate (0,0).  Furthermore, a profile can only have
certain shapes within its bounding rectangle.  The upper edge of the
profile coincides with the upper edge of the bounding rectangle, and
the right edge of the profile coincides with the right edge of the
bounding rectangle.  The path from (0,0) starting towards positive $y$
coordinates and ending at the lower-right corner is an alternating
sequence of $90^\circ$ turns, starting with a left turn.  It turns out
that ASTs can often be considered to have this shape.

We can represent a profile by a sequence of the points where the said
path makes a right turn, terminated by the point of the lower-right
corner.  We omit the upper-left corner, since it is always at (0,0).
We represent each point as a \texttt{cons} cell with the $x$
coordinate in the \texttt{car} and the $y$ coordinate in the
\texttt{cdr}.  The example profile in \refFig{fig-profile} is thus
represented as the list \texttt{((15 . 20) (25 . 25) (30 . 40))}.

The degenerate case is when the profile is a rectangle, in which case
the sequence of points is a singleton, containing only the point of
the lower-right corner.

\subsubsection{Combining two profiles vertically}

Let us now see how we can combine two profiles vertically.  Let us say
the upper profile is $P = $ ((x$_{1_p}$ . y$_{1_p}$) (x$_{2_p}$
. y$_{2_p}$) $\cdots$ (x$_{m_p}$ . y$_{m_p}$)) and the lower profile
is $Q = $ ((x$_{1_q}$ . y$_{1_q}$) (x$_{2_q}$ . y$_{2_q}$) $\cdots$
(x$_{n_q}$ . y$_{n_q}$)).

To combine the two, we find a suffix of $P$, say ((x$_{i_p}$
. y$_{i_p}$) $\cdots$ (x$_{m_p}$ . y$_{m_p}$)) such that x$_{i_p} \ge $
x$_{n_q}$.

Several cases can be distinguished.  The first case is when the suffix
is empty, i.e. there is no point in $P$ with an $x$ coordinate that is
greater than or equal to the width of $Q$.  This situation is
illustrated in \refFig{fig-profile-vertical-case-1}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-vertical-case-1.pdf_t}
\end{center}
\caption{\label{fig-profile-vertical-case-1}
Combining vertical profiles, case 1.}
\end{figure}

In \refFig{fig-profile-vertical-case-1}, the dotted lines together
with $Q$ indicate the combined profile.  The combined profile is
represented by $R = $ ((x$_{1_q}$ . y$_{1_q}$$+$y$_{m_p}$) (x$_{2_q}$
. y$_{2_q}$$+$y$_{m_p}$) $\cdots$ (x$_{n_q}$
. y$_{n_q}$$+$y$_{m_p}$)).  In other words, in order to obtain the
combined profile, we must add the $y$ coordinate of the upper profile
to every $y$ coordinate of the lower profile.

The second case is when the suffix contains a single point, so it is
simply ((x$_{m_p}$ . y$_{m_p}$)).  This situation is
illustrated in \refFig{fig-profile-vertical-case-2}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-vertical-case-2.pdf_t}
\end{center}
\caption{\label{fig-profile-vertical-case-2}
Combining vertical profiles, case 2.}
\end{figure}

As illustrated by \refFig{fig-profile-vertical-case-2}, the resulting
profile is represented by $R = $ ((x$_{1_q}$ . y$_{1_q}$$+$y$_{m_p}$)
(x$_{2_q}$ . y$_{2_q}$$+$y$_{m_p}$) $\cdots$ (x$_{m_p}$
. y$_{n_q}$$+$y$_{m_p}$)).  In other words, it is the same as case 1,
except that the $x$ coordinate of the last point in the resulting
sequence is x$_{m_p}$ rather than x$_{n_q}$, because it reflects the
width of the upper profile.

The third case is when the suffix contains more than one point, say
((x$_{i_p}$ . y$_{i_p}$) $\cdots$ (x$_{m_p}$ . y$_{m_p}$)).  This is
the general case, and can be subdivided further.  The general case is
illustrated in \refFig{fig-profile-vertical-case-3}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-vertical-case-3.pdf_t}
\end{center}
\caption{\label{fig-profile-vertical-case-3}
Combining vertical profiles, case 3, general.}
\end{figure}

As \refFig{fig-profile-vertical-case-3} illustrates, we can now
compact the combined profile so that there is partial vertical
overlap, thereby decreasing the amount of vertical blank space in the
rendering.  But, as illustrated by the dashed lines in
\refFig{fig-profile-vertical-case-3}, we must further subdivide this
case according to the shape of the lower-right corner of $P$.

Case 3a occurs when y$_{m_p}$$-$y$_{i_p}$ $\le$ y$_{n_q}$.  This case is
illustrated in \refFig{fig-profile-vertical-case-3a}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-vertical-case-3a.pdf_t}
\end{center}
\caption{\label{fig-profile-vertical-case-3a}
Combining vertical profiles, case 3a.}
\end{figure}

As illustrated by \refFig{fig-profile-vertical-case-3a}, the resulting
profile is represented by $R = $ ((x$_{1_q}$ . y$_{1_q}$$+$y$_{i_p}$)
(x$_{2_q}$ . y$_{2_q}$$+$y$_{i_p}$) $\cdots$ (x$_{m_p}$
. y$_{n_q}$$+$y$_{i_p}$)).

Case 3b occurs when y$_{m_p}$$-$y$_{i_p}$ $>$ y$_{n_q}$.  In this
case, we take the suffix ((x$_{i_p}$ . y$_{i_p}$) $\cdots$ (x$_{m_p}$
. y$_{m_p}$)) and we search for the first points $j\ge i$ and $j+1$ such
that y$_{{j+1}_p}$$-$y$_{i_p}$$>$y$_{n_q}$.  Two points like this must exist,
because the suffix already contains at least two points, and we know
that y$_{m_p}$$-$y$_{i_p}$ $>$ y$_{n_q}$.  This case is illustrated in
\refFig{fig-profile-vertical-case-3b}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-vertical-case-3b.pdf_t}
\end{center}
\caption{\label{fig-profile-vertical-case-3b}
Combining vertical profiles, case 3b.}
\end{figure}

As illustrated by \refFig{fig-profile-vertical-case-3b}, the resulting
profile is represented by $R = $ ((x$_{1_q}$ . y$_{1_q}$$+$y$_{i_p}$)
(x$_{2_q}$ . y$_{2_q}$$+$y$_{i_p}$) $\cdots$ (x$_{j_p}$
. y$_{n_q}$$+$y$_{i_p}$) ((x$_{{j+1}_p}$ . y$_{{j+1}_p}$) $\cdots$
(x$_{m_p}$ . y$_{m_p}$)).

\subsubsection{Combining two profiles horizontally}

Now let us turn to combining two profiles horizontally.  As it turns
out, the left profile then represents a single AST node, so it is
always a rectangle.  This fact makes the combination easier.

Let's say the left profile is $P = $ ((x$_p$ . y$_p$)) and the right
profile is $Q = $ ((x$_{1_q}$ . y$_{1_q}$) (x$_{2_q}$ . y$_{2_q}$)
$\cdots$ (x$_{n_q}$ . y$_{n_q}$)).

There are two cases to distinguish.  The first case is when y$_p$ $\ge$
y$_{n_q}$.  This case is illustrated in
\refFig{fig-profile-horizontal-case-1}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-horizontal-case-1.pdf_t}
\end{center}
\caption{\label{fig-profile-horizontal-case-1}
Combining horizontal profiles, case 1.}
\end{figure}

In this case, the resulting profile is $R = $ ((x$_p$$+$x$_{n_q}$ . y$_p$)).

The second case is when y$_p$ $<$ y$_{n_q}$.  There are then two
sub-cases to consider.  The first sub-case is when y$_{1_q}$$>$y$_p$.
This case is illustrated in \refFig{fig-profile-horizontal-case-2a}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-horizontal-case-2a.pdf_t}
\end{center}
\caption{\label{fig-profile-horizontal-case-2a}
Combining horizontal profiles, case 2a.}
\end{figure}

In this case, the resulting profile is $R = $ ((x$_p$ . y$_p$)
(x$_p$$+$x$_{1_q}$ . y$_{1_q}$) (x$_p$$+$x$_{2_q}$ . y$_{2_q}$)
$\cdots$ (x$_p$$+$x$_{n_q}$ . y$_{n_q}$)).

The second sub-case is when y$_{1_q}$$\le$y$_p$.  We then take the
profile $Q$ and we search for the first points $j$ and $j+1$, such
that y$_{{j+1}_q}$$>$y$_p$.  Two points like this must exist, because
the $Q$ already contains at least two points, and we know that
y$_{1_q}$ $\le$ y$_p$ and that y$_{n_q}$ $>$ y$_p$.
This case is illustrated in \refFig{fig-profile-horizontal-case-2b}.

\begin{figure}
\begin{center}
\inputfig{fig-profile-horizontal-case-2b.pdf_t}
\end{center}
\caption{\label{fig-profile-horizontal-case-2b}
Combining horizontal profiles, case 2b.}
\end{figure}

$R = $ ((x$_p$$+$x$_{j_q}$ . y$_p$)
(x$_p$$+$x$_{{j+1}_q}$ . y$_{{j+1}_q}$)
$\cdots$ (x$_p$$+$x$_{n_q}$ . y$_{n_q}$)).
